<!DOCTYPE html>
<html lang="zh-CN">
<head>
    <!-- 文件字符编码 -->
    <meta charset="utf-8">
    <!-- 兼容手机,禁止缩放 -->
    <!--		<meta name="viewport" content="width=device-width,initial-scale=1,minimum-scale=1,maximum-scale=1,user-scalable=no" />-->
    <meta content="width=device-width,initial-scale=1,minimum-scale=1,maximum-scale=1,user-scalable=no,viewport-fit=cover"
          name="viewport">
    <!-- 告诉IE使用最新内核 -->
    <meta content="ie=edge" http-equiv="X-UA-Compatible">
    <title>排序算法2</title>
    <style type="text/css">

    </style>
</head>
<body>

<div class="container">
    排序算法234543634645
</div>
<script>
    let arrTest = [2,5,45,1,0,957,8,100,6,9,7,784,5,196,54];
    console.log(`数组:`,arrTest)

    //选择排序
    let min = (numbers)=>{
        if (numbers.length>2){
            return min([numbers[0],min(numbers.slice(1))]);
        }else {
            return Math.min.apply(null,numbers)
        }
    }
    let sort = (numbers)=> {
        if (numbers.length>2){
            let minNumber = min(numbers);
            let minIndex = numbers.indexOf(minNumber);
            numbers.splice(minIndex,1);
            return [minNumber].concat(sort(numbers));
        }else {
            return numbers[0]<numbers[1]?numbers:numbers.reverse();
        }
    }
    // console.log(`选择排序:`,sort(arrTest));

    //快速排序
    let quickSort = (arr) =>{
        if (arr.length<=1) return arr;
        let pivotIndex = Math.floor(arr.length/2);
        let pivot = arr.splice(pivotIndex,1)[0];
        let left = [];
        let right = [];
        for (let i = 0;i<arr.length;i++){
            arr[i]<pivot?left.push(arr[i]):right.push(arr[i]);
        }
        return quickSort(left).concat(pivot,quickSort(right));
    }
    // console.log(`快速排序:`,quickSort(arrTest));

    //归并排序
    let mergeSort = (arr)=>{
        let len = arr.length;
        if (len===1) return arr;
        let leftArr = arr.slice(0,Math.floor(len/2));
        let rightArr = arr.slice(Math.floor(len/2));
        return merge(mergeSort(leftArr),mergeSort(rightArr));
    }
    let merge = (leftArr,rightArr)=>{
        if (leftArr.length === 0) return rightArr;
        if (rightArr.length === 0) return leftArr;
        return leftArr[0]<rightArr[0] ?
            [leftArr[0]].concat(merge(leftArr.slice(1),rightArr)) :
            [rightArr[0]].concat(merge(leftArr,rightArr.slice(1)))
    }
    // console.log(`归并排序:`,mergeSort(arrTest));

    //计数排序
    let cuntSort = arr =>{
        let hasTable = {},min=0,max=0,result=[];
        for (let i=0;i<arr.length;i++){
            if (!(arr[i] in hasTable)){
                hasTable[arr[i]] = 1;
            }else{
                hasTable[arr[i]] +=1;
            }
            if (arr[i] > max){max=arr[i]}
            if (arr[i] < min){min=arr[i]}
        }
        for (let j=min;j<=max;j++){
            if (j in  hasTable){
                for (let k=0;k<hasTable[j];k++){
                    result.push(j);
                }
            }
        }
        return result;
    }
    // console.log(`计数排序:`,cuntSort(arrTest));

</script>
</body>
</html>
